package org.aplombh.java.awcing.basic.basics.sort.quickSort;

import java.util.Scanner;
import java.util.stream.IntStream;

import static org.regotto.common.Utils.swap;

/**
 * 给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
 * <p>
 * 输入格式
 * 第一行包含两个整数 n 和 k。
 * <p>
 * 第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
 * <p>
 * 输出格式
 * 输出一个整数，表示数列的第 k 小数。
 * <p>
 * 数据范围
 * 1≤n≤100000,
 * 1≤k≤n
 * 输入样例：
 * 5 3
 * 2 4 1 5 3
 * 输出样例：
 * 3
 */

public class KthNumber_786 {

    private static final int N = 100010;

    public static int kthNumber(int[] ints, int left, int right, int k) {

        if (left == right) return ints[left];
        int x = ints[left + right >> 1], i = left - 1, j = right + 1;

        while (i < j) {
            while (ints[++i] < x) ;
            while (ints[--j] > x) ;
            if (i < j) swap(ints, i, j);
        }
        // count the numbers on the left partition
        int sumLeftPartition = j - left + 1;

        //if the count greater than k, the kth number is in left partition
        if (k <= sumLeftPartition) return kthNumber(ints, left, j, k);

        // Otherwise, compute the (k - sumLeftPartition)th number in the right partition
        return kthNumber(ints, j + 1, right, k - sumLeftPartition);

    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] ints = new int[n];
        IntStream.range(0, n).forEach(i -> ints[i] = scanner.nextInt());
        System.out.println(kthNumber(ints, 0, n - 1, k));
    }
}
